MAX = 10000 # 定义最大路径权值。

class DirectedWeightGraph:
    def __init__(self, n: int) -> None:
        self.vertices = list(range(n)) # 顶点集合
        self.edges = [[MAX] * n for _ in range(n)] # 邻接矩阵，元素值为边的权重
        self.V = n # 顶点个数V
        self.E = 0 # 边的个数E

    # 往图中添加边<u, v>, 权重为weight
    def addEdge(self, u: int, v: int, weight: int) -> None:
        self.edges[u][v] = weight
        self.E += 1

# 求多段图的最短路径
def solve(dwg: DirectedWeightGraph) -> None:
    n = dwg.V # 图的顶点总数

    # 初始化cost数组与path数组

    # cost数组记录最短路径长度
    cost = [dwg.edges[0][i] for i in range(n)] 

    # path数组记录最短路径的上一节点位置
    path = [-1] * n 

    # 初始化源点状态
    cost[0] = path[0] = 0

    # 从j=1开始，考察从源点0到顶点j的所有入边
    for j in range(1, n):
        min_cost = MAX
        for i in range(j):
            # 没有边连接, 跳过
            if dwg.edges[i][j] >= MAX:  
                continue
            
            # 有边连接，更新cost[j]、path[j]
            if cost[i] + dwg.edges[i][j] <= min_cost:
                cost[j] = cost[i] + dwg.edges[i][j]
                min_cost = cost[j]
                path[j] = i
            

    # 使用栈还原path并输出
    pathStk = []
    i = n - 1 
    while i != 0:
        pathStk.append(i)
        i = path[i]
    print('最短路径: 0', end=' ') # 源点
    while pathStk: 
        print('->',  pathStk.pop(), end=' ')
    print() 

    # 输出最短路径长度
    print('最短路径长度:', cost[-1])

# __main__
# 创建顶点个数为10的有向加权图并初始化所有的路径
n = 10 # 顶点个数为10
dwg = DirectedWeightGraph(n)
for u, v, w in [(0, 1, 4), (0, 2, 2), (0, 3, 3), (1, 4, 9), (1, 5, 8), (2, 4, 6), (2, 5, 7), (2, 6, 8), (3, 5, 4), (3, 6, 7), (4, 7, 5), (4, 8, 6), (5, 7, 8), (5, 8, 6), (6, 7, 6), (6, 8, 5), (7, 9, 7), (8, 9, 3)]:
    dwg.addEdge(u, v, w)
solve(dwg) # 调用核心方法求解最短路径